package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author bc
 * @Description: LRU 缓存
 * @date 2024/03/18
 */
@SuppressWarnings("ALL")
public class BC_146_LRU {

    /**
     * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
     * 实现 LRUCache 类：
     * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
     * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     *
     * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
     * 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     *
     * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
     *
     * https://leetcode.cn/problems/lru-cache/description/
     */
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        System.out.println(lruCache.get(1));
        lruCache.put(3, 3);
        System.out.println(lruCache.get(2));

    }

    static class LRUCache {

        /**
         * 当前数量
         */
        private Integer cnt;

        /**
         * 总量
         */
        private Integer sum;

        /**
         * 存储key-value
         */
        private Map<Integer, TreeNode> map;

        class TreeNode {
            private TreeNode pre;

            private TreeNode next;

            private Integer key;

            private Integer value;

            public TreeNode() {
            }

            public TreeNode(Integer key, Integer value) {
                this.key = key;
                this.value = value;
            }
        }

        TreeNode head;

        TreeNode tail;

        public LRUCache(int capacity) {
            cnt = 0;
            sum = capacity;
            map = new HashMap<>();
            head = new TreeNode();
            tail = new TreeNode();
            head.pre = null;
            head.next = tail;
            tail.pre = head;
            tail.next = null;
        }

        public int get(int key) {
            TreeNode node = map.getOrDefault(key, null);
            if (null == node) {
                return -1;
            }
            if (node.value != -1) {
                deleteNode(node);
                addNode(node);
                map.put(key, node);
            }
            return node.value;
        }

        public void put(int key, int value) {
            TreeNode node = map.getOrDefault(key, null);
            if (node != null) {
                deleteNode(node);
                addNode(node);
                node.key = key;
                node.value = value;
                map.put(key, node);
                return ;
            }
            if (cnt >= sum) {
                TreeNode tmp = tail.pre;
                tmp.value = -1;
                deleteNode(tmp);
                map.put(tmp.key, null);
            }
            node = new TreeNode(key, value);
            addNode(node);
            map.put(key, node);
            cnt++;
        }

        void deleteNode(TreeNode node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        void addNode(TreeNode node) {
            node.next = head.next;
            head.next.pre = node;
            node.pre = head;
            head.next = node;
        }
    }
}
